#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>


using namespace std;

class Solution1 {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        sort(coins.begin(), coins.end());
        int s = 1; int ans = 0; int i = 0;
        while (s <= target)
        {
            if (i < coins.size() && coins[i] <= s)
            {
                s += coins[i++];
            }
            else
            {
                s *= 2;
                ans++;
            }
        }
        return ans;
    }
};

class Solution2 {
public:
    bool isValidSerialization(string preorder) {
        if (preorder == "#") return true;
        if (preorder[0] == '#' && preorder.size() > 1) return false;
        string str;
        for (int i = 0; i < preorder.size(); ++i)
        {
            if (preorder[i] >= '0' && preorder[i] <= '9')
            {
                str += '1';
                while (i < preorder.size() && preorder[i] != ',') ++i;
            }
            else
            {
                str += '#';
                i++;
            }
        }
        stack<int> st; st.push(2);
        for (int i = 1; i < str.size(); ++i)
        {
            if (st.empty()) return false;
            if (--st.top() == 0) st.pop();
            if (str[i] == '1')
                st.push(2);
        }
        return st.empty();
    }
};

class Solution3
{
public:
    void solve()
    {
        int n, V;
        cin >> n >> V;
        vector<int> w(n + 1); vector<int> v(n + 1);
        for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
        vector<vector<int>> dp1(n + 1, vector<int>(V + 1));
        vector<vector<int>> dp2(n + 1, vector<int>(V + 1));
        for (int j = 1; j <= V; ++j) dp2[0][j] = -1;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= V; ++j)
            {
                int dv = j - v[i];
                dp1[i][j] = dp1[i - 1][j];
                dp2[i][j] = dp2[i - 1][j];
                if (dv >= 0)
                {
                    dp1[i][j] = max(dp1[i][j], dp1[i - 1][dv] + w[i]);
                    if (dp2[i - 1][dv] != -1) dp2[i][j] = max(dp2[i][j], dp2[i - 1][dv] + w[i]);
                }
            }
        }
        cout << dp1[n][V] << endl;
        cout << (dp2[n][V] == -1 ? 0 : dp2[n][V]) << endl;
    }
};

class Solution4 {
public:
    string finalString(string s) {
        int n = s.size();
        string res;
        for (int i = 0; i < n; ++i)
        {
            if (s[i] != 'i')
            {
                res += s[i];
            }
            else
            {
                int cnt = 0;
                while (i < n && s[i] == 'i') ++i, ++cnt;
                if (cnt & 1) reverse(res.begin(), res.end());
                --i;
            }
        }
        return res;
    }
};

int main()
{

    return 0;
}
